package problems.practice;

import utils.beans.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * 1382. 将二叉搜索树变平衡
 * <p>https://leetcode.cn/problems/balance-a-binary-search-tree/</p>
 *
 * @author habitplus
 * @since 11:31, 2022/10/4
 */
public class T1382 {
    List<TreeNode> nodes = new ArrayList<>();

    public TreeNode balanceBST(TreeNode root) {
        inOrder(root);
        return buildBinaryBalanceTree(0, nodes.size() - 1);
    }

    private TreeNode buildBinaryBalanceTree(int low, int high) {
        if (low > high) return null;
        int mid = (low + high) / 2;

        TreeNode node = nodes.get(mid);
        node.left = buildBinaryBalanceTree(low, mid - 1);
        node.right = buildBinaryBalanceTree(mid + 1, high);
        return node;
    }

    private void inOrder(TreeNode root) {
        if (root == null) return;
        inOrder(root.left);
        nodes.add(root);
        inOrder(root.right);
    }
}
